#include "parse.h"
#include "check.h"
#include "operator.h"
#include "globals.h"

static
void    DumpRule(FILE* Handle, TRule* Rule)
    {
    fprintf(Handle, "    -> ");
    SymbolListDump(Handle, Rule->Symbols, " ");
    fprintf(Handle, "\n");
    }

/* CheckLR0RuleDup() - check for duplicate rules.
 *
 * We already checked for duplicate rules in CommonLeft(),
 * but operator abbreviations add an extra level of complexity
 * that gets handled here.
 *
 * main()
 *     ...
 *     CheckLR0Rules()
 *         CheckLR0Rule()
 *         CheckLR0RuleDup()
 *     ComputeAllLR0()
 *     ...
 */
static
void    CheckLR0RuleDup(TSymbol* NonTerm, TRule* RuleA, TRule* RuleB)
    {
    int         NSymA, NSymB, iProdItem;
    TSymbol*    SymA;
    TSymbol*    SymB;
    SYMBOLS     ListA, ListB, ListIntersect;


    NSymA   = RuleItemCount(RuleA);
    NSymB   = RuleItemCount(RuleB);
    
    /* if both rhs are same length, might be dup */
    if(NSymA == NSymB)
        {
printf("Check for rule dups between:\n");
DumpRule(stdout, RuleA);
DumpRule(stdout, RuleB);
        for(iProdItem=0; iProdItem < NSymA; ++iProdItem)
            {
            SymA    = SymbolListGet(RuleA->Symbols, iProdItem);
            SymB    = SymbolListGet(RuleB->Symbols, iProdItem);

            if(!SymbolIsEqual(SymA, SymB) && !(SymA->OpAbbrev || SymB->OpAbbrev))
                break;
            else if(SymbolIsEqual(SymA,SymB))
                continue;

            /* now they are not equal, and one or both is an operator abbreviation */
                
            /* embedded actions not allowed; handled elsewhere */
            assert(!(SymbolIsAction(SymA) || SymbolIsAction(SymB)));

            printf("operator abbrev involved!\n");
            ListA   = SymA->OpAbbrev ? SymbolListCopy(NULL, SymA->OpAbbrev) : SymbolListAdd(NULL, SymA);
            ListB   = SymB->OpAbbrev ? SymbolListCopy(NULL, SymB->OpAbbrev) : SymbolListAdd(NULL, SymB);
            ListIntersect = SymbolListIntersect(ListA, ListB);
            if(ListIntersect)
                {
                /* simple duplicates were handled elsewhere */
                assert(!SymbolIsEqual(SymA,SymB));

                ErrorPrologue(ERROR_CLASH_IN_OP_ABBREV);
                Error("These two rules of '%s' intersect:\n", SymbolStr(NonTerm));
                DumpRule(stderr, RuleA);
                DumpRule(stderr, RuleB);
                Error("because the operator abbreviator");
                if(SymA->OpAbbrev)
                    {
                    Error("%s '%s'", SymB->OpAbbrev?"s":"", SymbolStr(SymA));
                    if(SymB->OpAbbrev)
                        Error(" and %s both contain ", SymbolStr(SymB));
                    else
                        Error(" contains ");
                    }
                else if(SymB->OpAbbrev)
                    Error(" '%s' contains ", SymbolStr(SymB));
                Error("%s.\n", SymbolStr(SymbolListGet(ListIntersect, 0)));
                ErrorEpilog(-1);

                SymbolListDestroy(ListA);
                SymbolListDestroy(ListB);
                if(ListIntersect)
                    SymbolListDestroy(ListIntersect);
                }
            else if(!SymbolIsEqual(SymA,SymB))
                break;
            /* else, looks like a duplicate so far, so keep going */
            }
        }
    }

#if 0
/* CheckOpAbbrev()
 *
 * We hit a nonterminal in an LR(0) rule that was not declared as
 * an operand. Here, we see if it could not possibly be an
 * operator abbreviation. If it can't be, then we fail with an
 * error message. If it could be an operator abbreviation, then
 * we return the list of operators that this nonterminal represents.
 */
static
SYMBOLS CheckOpAbbrev(TToken Token, TSymbol* NonTerm)
    {
    int         iRule, NRules, iSymbol;
    TRule**     Rover;
    TRule*      Rule;
    TSymbol*    Symbol;
    SYMBOLS     Result = NULL;
    char        Buffer[1024];

    DumpVerbose("CheckOpAbbrev('%s')\n", SymbolStr(NonTerm));
    
    NRules  = NonTerm->NRules;
    for(iRule=0; iRule < NRules; ++iRule)
        {
        Rule    = NonTerm->Rules[iRule];

        for(iSymbol=0; (Symbol=SymbolListGet(Rule->Symbols, iSymbol)) != NULL; ++iSymbol)
            {
            if(SymbolIsAction(Symbol))
                {
                sprintf(Buffer, "its production rules include an action, not just operators.");
                break;
                }
            else if(SymbolGetBit(Symbol, TERMINAL) == FALSE)
                {
                sprintf(Buffer, "its production rules include a nonterminal ('%s'), not just operators.",
                    SymbolStr(Symbol));
                break;
                }
            else if(iSymbol == 1)
                {
                sprintf(Buffer, "at least one of its rules contains more than one terminal.\n"
                    "%s -> %s %s %s\n",
                    SymbolStr(NonTerm), SymbolListGet(Rule->Symbols, 0), Symbol,
                    SymbolListCount(Rule->Symbols) > 1 ? "..." : "");
                break;
                }
            else
                Result  = SymbolListAdd(Result, Symbol);
            }
        if(iSymbol < SymbolListCount(Rule->Symbols))
            break;
        }
    if(iRule < NRules)
        SyntaxError(ERROR_BAD_OP_ABBREV, Token,
            "%s was not declared as an operand, so I thought it might be an operator abbreviation. However, \n%s",
            SymbolStr(NonTerm), Buffer);
    if(Globals.Dump && Globals.Verbose)
        {
        if(Result)
            {
            Dump("    returns ");
            SymbolListDump(stdout, Result, " ");
            Dump("\n");
            }
        else
            Dump("    returns NULL\n");
        }

    return Result;
    }

/* CheckLR0Rule() - check a single rule of a LR0 nonterminal.
 */
static
void    CheckLR0Rule(TSymbol* NonTerm, TRule* Rule)
    {
    int         iProdItem, NProdItems, iOperator, OpType;
    TSymbol*    Symbol;
    TOperator*  Operator;
    char        Pattern[MAX_OPERATOR_PATTERN+1];
    char*       PatRover = Pattern;
    char*       QMark;

    NProdItems  = SymbolListCount(Rule->Symbols);

    /* Make sure symbols in rule are all either
     * operators or operands.
     */
    for(iProdItem=0; iProdItem < NProdItems; ++iProdItem)
        {
        Symbol  = SymbolListGet(Rule->Symbols, iProdItem);
        if(SymbolIsAction(Symbol))
            {
            if(iProdItem != (NProdItems-1))
                {
                ErrorPrologue(ERROR_NO_EMBEDDED_ACTION);
                Error("Embedded actions not allowed in operator precedence rule:\n%s", SymbolStr(NonTerm));
                DumpRule(stderr, Rule);
                ErrorEpilog(-1);
                }
            else
                --NProdItems;   /* revise to reflect "real" count */
            }
        else if(Symbol->Operand)
            {
            *PatRover++ = 'X';
            assert(PatRover - Pattern < MAX_OPERATOR_PATTERN);
            }
        else if((Operator=OperatorFindOpSym(NULL, Symbol)) != NULL)
            *PatRover++ = '.';
        else if(SymbolGetBit(Symbol, SYM_TERMINAL))
            SyntaxError(ERROR_NOT_OPERATOR_OR_OPERAND, Rule->Tokens[iProdItem],
                "'%s' is a terminal used by '%s' but was not declared as an operator or operand.",
                SymbolStr(Symbol), SymbolStr(NonTerm)
                );
        /* by now, we know it's a nonterminal not declared as operator or operand */
        else
            *PatRover++ = '?';  /* remember it as possible error or operator abbreviation */
        }
    *PatRover = '\0';

    Symbol  = NULL; /* we'll set it to operator abbreviation, if any */
    /* were there one or more undeclared nonterminals? */
    QMark = strchr(Pattern, '?');
    if(QMark)
        {
        SYMBOLS Operators;

        Symbol = SymbolListGet(Rule->Symbols, QMark-Pattern);
        /* is it potentially legal if nonterminal is an operator abbreviation? */
        if(!strcmp(Pattern, "X?"))
            OpType = OP_PRE_UNARY;
        else if(!strcmp(Pattern, "?X"))
            OpType = OP_POST_UNARY;
        else if(!strcmp(Pattern, "X?X"))
            OpType = OP_BINARY;
        else 
            OpType  = OP_UNKNOWN;
        fprintf(stdout, "QMark pattern='%s'\n", Pattern);
        if(OpType == OP_UNKNOWN)
            SyntaxError(ERROR_NOT_OPERATOR_OR_OPERAND, Rule->Tokens[QMark-Pattern],
                "'%s' is a nonterminal used by '%s' but was not declared as an operator or operand.\n"
                "The rule isn't the right form for '%s' to be an operator abbreviation, either.\n",
                SymbolStr(Symbol), SymbolStr(NonTerm), SymbolStr(Symbol)
                );
        *QMark  = '.';  /* assume it's going to be a legal operator */
        /* because we think there's an operator abbreviation involved,
         * have to make sure all the possibilities match declared operators.
         */
        Symbol->OpAbbrev = Operators   = CheckOpAbbrev(Rule->Tokens[QMark-Pattern], Symbol);
    fprintf(stdout, "'%s' is an operator abbreviation\n", SymbolStr(Symbol));

        }

fprintf(stdout, "pattern='%s'\n", Pattern);

    /* OK, it's all operators and operands, but does it match an operator declaration? */
    if(strcmp(Pattern, "X"))
        {
        Operator = NULL;
        for(iOperator=0; (Operator=OperatorGet(iOperator)) != NULL; ++iOperator)
            {
//        fprintf(stdout, "Compare op '%s' to '%s'\n", Pattern, Operator->Pattern);
            if(!strcmp(Pattern, Operator->Pattern))
                /* ??? TODO: make sure operators actually match */
                break;
            }
        if(Operator == NULL)
            {
            ErrorPrologue(ERROR_NO_MATCHING_OPERATOR_PATTERN);
            Error("This rule: %s ", SymbolStr(NonTerm));
            DumpRule(stderr, Rule);
            Error("\ndoesn't seem to correspond to any of operators you declared.\n");
            ErrorEpilog(-1);
            }
        }
    }

#if 0
        else if(
            {
            
            }

        else if(CheckOpAbbrev(Symbol, Buffer))
            *PatRover++ = '.';
        else
            {

            *Rover= '\0';
            
            SyntaxError(ERROR_NOT_OPERATOR_OR_OPERAND, Rule->Tokens[iProdItem],
                "'%s': was not declared as an operator or operand and\ndoesn't appear to be a set of unary or binary operators.",
                SymbolStr(Symbol)
                );
            }
#endif


/* CheckLR0Rules() - make sure expression rules are legal.
 *
 * Note that this has the important side-effect of setting the
 * IsOpAbbrev flag in nonterminals that appear to be legal operator
 * abbreviations.
 */
void    CheckLR0Rules(void)
    {
    SymIt       NonTerm;
    int         NRules, iRule, jRule;

    Dump("CheckLR0Rules()\n");

    /* for each bottom-up nonterminal */
    NonTerm = SymItNew(Globals.NonTerms);
    while(SymbolIterate(&NonTerm))
        if(NonTerm.Symbol->OperatorTrigger)
            {
            NRules  = NonTerm.Symbol->NRules;
            for(iRule = 0; iRule < NRules; ++iRule)
                CheckLR0Rule(NonTerm.Symbol, NonTerm.Symbol->Rules[iRule]);
            }
    /* now we've identified operator abbreviations, so look for duplicate rules */
    NonTerm = SymItNew(Globals.NonTerms);
    while(SymbolIterate(&NonTerm))
        if(NonTerm.Symbol->OperatorTrigger)
            {
            NRules  = NonTerm.Symbol->NRules;
            for(iRule = 0; iRule < (NRules-1); ++iRule)
                for(jRule = iRule+1; jRule < NRules; ++jRule)
                    CheckLR0RuleDup(NonTerm.Symbol, NonTerm.Symbol->Rules[iRule], NonTerm.Symbol->Rules[jRule]);
            }
    Dump("CheckLR0Rules() done\n");
    }

#endif

/* GetSingles() - list of single non-terminals this nonterminal can produce directly
 *
 * Algorithm (roughly) from Coco book, pp.150-151.
 */
static
SYMBOLS     GetSingles(TSymbol* Left)
    {
    SYMBOLS Result;
    TRule** Rover;

    Result  = SymbolListCreate();
    Rover   = Left->Rules;
    if(Rover)for(; *Rover; ++Rover)
        {
        TRule*  Rule        = *Rover;
        SymIt   ProdItem    = SymItNew(Rule->Symbols);

        while(SymbolIterate(&ProdItem))
            if(!SymbolIsAction(ProdItem.Symbol))
                {
                int     RhsNullable;

                /* can't derive a single non-terminal if we have to emit a terminal */
                if(SymbolGetBit(ProdItem.Symbol, SYM_TERMINAL))
                    break;
                /* figure out if everything to the right is nullable */
                RhsNullable     = RuleNullable(Rule, ProdItem.Index);

                /* We're examining a nonterminal from the rhs. All symbols to the
                 * left (if any) are nullable. So, if all the symbols to the right
                 * are also nullable, then we can derive a string containing only
                 * this nonterminal.
                 */
                if(RhsNullable)
                    SymbolListAddUnique(Result, ProdItem.Symbol);
                /* if it's not nullable, then no point in looking further to the right
                 */
                if(!ProdItem.Symbol->Nullable)
                    break;
                }
        }
    if(Globals.Dump && Globals.Verbose)
        {
        Dump("GetSingles('%s') = ", SymbolStr(Left));
        SymbolListDump(stdout, Result, ", ");
        Dump("\n");
        }
    return Result;
    }

/* CheckCircularity() - detect any cycles in the graph.
 *
 */
int    CheckCircularity(void)
    {
    SYMBOLS     Left=NULL, Right=NULL;
    SymIt       NonTerm;
    int         Changed;
    int         ErrorCount  = 0;

    Dump("CheckCircularity()\n");
    /* for each nonterminal */
    NonTerm = SymItNew(Globals.NonTerms);
    while(SymbolIterate(&NonTerm))
        if(!SymbolIsAction(NonTerm.Symbol))
            {
            SYMBOLS Singles;
            SymIt   Single;

            /* fetch all the single nonterminals it can directly derive */
            Singles = GetSingles(NonTerm.Symbol);

            /* for each of the right-hand-side single nonterminals */
            Single  = SymItNew(Singles);
            while(SymbolIterate(&Single))
                {
                /* Add them to the list of graph nodes. Conceptually,
                 * we are recording the fact that 'Left' can derive a
                 * string that contains only a 'Right'.
                 */
                Left    = SymbolListAdd(Left, NonTerm.Symbol);
                Right   = SymbolListAdd(Right, Single.Symbol);
                }
            SymbolListDestroy(Singles);
            }
    /* remove edges from the graph that aren't part of any cycle */
    do  {
        SymIt       GraphNode;

        Changed = FALSE;
        GraphNode   = SymItNew(Left);
        while(SymbolIterate(&GraphNode))
            {
            TSymbol*    LeftSym     = GraphNode.Symbol;
            TSymbol*    RightSym    = SymbolListGet(Right, GraphNode.Index);

            /* So, we know that 'LeftSym' can derive a 'RightSym'.
             * But, if nothing derives a 'LeftSym', or 'RightSym'
             * derives nothing, then this connection can't be part of
             * any cycle, so remove it from graph.
             */
            if(!SymbolListContains(Right, LeftSym) || !SymbolListContains(Left, RightSym))
                {
                SymbolListDelete(Left, GraphNode.Index);
                SymbolListDelete(Right, GraphNode.Index);
                --GraphNode.Index;
                Changed = TRUE;
                }
            }
        } while(Changed);

    /* if graph is not empty, then there is one or more circular symbols */
    if(SymbolListCount(Left) > 0)
        {
        /* TODO: need a nice description of how they are circular!
         *
         * do while FoundNewCycle
         * for each symbol in Left
         *     find biggest cycle it is part of
         *     if cycle not in list of previously found cycles
         *         add cycle to list
         *         print out cycle
         */
        fprintf(stderr, "Circular symbols: \n");
        SymbolListDump(stderr, Left, ", ");
        fprintf(stderr, "\n");
        SymbolListDump(stderr, Right, ", ");
        fprintf(stderr, "\n");
        ++ErrorCount;
        }
    SymbolListDestroy(Left);
    SymbolListDestroy(Right);

    Dump("CheckCircularity() returns %d\n", ErrorCount);
    return ErrorCount;
    }

/*  CheckCompleteness() - Make sure all non-terminals have a rule.
 *                                                                
 */
int    CheckCompleteness(void)
    {
    TRule** Rover;
    int     iNonTerm, jNonTerm;
    int     NNonTerms;
    int     ErrorCount = 0;

    NNonTerms   = SymbolListCount(Globals.NonTerms);

    for(iNonTerm = 0; iNonTerm < NNonTerms; ++iNonTerm)
        {
        TSymbol*    Undefined;

        Undefined     = SymbolListGet(Globals.NonTerms, iNonTerm);
        if(!SymbolIsAction(Undefined) && Undefined->Rules == NULL)
            {
            ++ErrorCount;
            fprintf(stderr, 
                    "Undefined non-terminal '%.*s'. It was referenced:\n",
                    Undefined->Name.TextLen,
                    Undefined->Name.Text);
            for(jNonTerm=0; jNonTerm < NNonTerms; ++jNonTerm)
                {
                TSymbol*    Temp = SymbolListGet(Globals.NonTerms, jNonTerm);

                /* for each production of this non-terminal */
                Rover   = Temp->Rules;
                if(Rover)for(; *Rover; ++Rover)
                    {
                    int     iSymbol, NSymbols;
                    TRule*  Rule    = *Rover;
        
                    assert(Rule != NULL);
        
                    NSymbols    = SymbolListCount(Rule->Symbols);
                    for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
                        {
                        TSymbol*    Rhs = SymbolListGet(Rule->Symbols, iSymbol);
        
                        assert(Rhs != NULL);
                        if(Rhs == Undefined)
                            {
                            TContext    Context;

                            if(Rule->Tokens)
                                {
                                Context     = InputGetContext(Rule->Tokens[iSymbol].Text);
                                fprintf(stderr, "     on Line %d: by '%.*s'\n    '%.*s'\n",
                                    Context.LineNumber,
                                    Temp->Name.TextLen, Temp->Name.Text,
                                    Context.LineLen, Context.LineStart);
                                }
                            else
                                fprintf(stderr, "    by an internally generated rule.\n");
                            }
                        }
                    }

                }
            }
        }
    return ErrorCount;
    }

/* CheckReachability() - are all non-terminals reachable from start symbol?
 */
static
void  MarkReached(SYMBOLS Reached, TSymbol* NonTerm)
    {
    TRule** Rover;

    assert(NonTerm != NULL);
    
    /* if this symbol not already marked as "reached" */
    if(!SymbolIsAction(NonTerm) && !SymbolListContains(Reached, NonTerm))
        {
        assert(SymbolGetBit(NonTerm, SYM_TERMINAL) == FALSE);

        /* mark this symbol as "reached" */
        SymbolListAdd(Reached, NonTerm);

        /* for each production of this non-terminal */
        Rover   = NonTerm->Rules;
        if(Rover)for(; *Rover; ++Rover)
            {
            int     iSymbol, NSymbols;
            TRule*  Rule    = *Rover;

            assert(Rule != NULL);

            /* for each symbol of this production */
            NSymbols    = SymbolListCount(Rule->Symbols);
            for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
                {
                TSymbol*    Rhs = SymbolListGet(Rule->Symbols, iSymbol);

                assert(Rhs != NULL);
                /* mark as "reached" each non-terminal in the production */
                if(!SymbolIsTerminal(Rhs))
                    MarkReached(Reached, Rhs);
                }
            }
        }
    }


/* CheckReachability() - are all symbols reachable from start symbol?
 *
 * Note that a single typo for a top-level non-terminal can create an
 * unreadable cascade, as some/all the children of that single typo then
 * get listed as non-reachable. We really want a way to point out the real
 * root of the problem.
 *
 * Note that there's no guarantee of a single "root" of the orphaned nodes.
 * For example, suppose we forgot to make A reachable in a grammar that contains:
 *     A : B ';' ;
 *     B : ident | A ;
 * When there's a cycle, there's no easy way to programmatically guess whether
 * it was a failure to mention A, B, or both that is the "real" user mistake.
 * But a more normal problem is this:
 *     program : module TK_END ;
 *     Module : // all the rest of the productions!
 * Here, a single typo makes nearly all the non-terminals unreachable, producing
 * a huge list of "problems", when we really just want to point out that
 * 'Module' is the cause for the rest of them being unreachable.
 *
 * Our algorithm goes as follows. First, make a list of all the non-terminals
 * not reached. For each non-terminal not reached, make a list of all the
 * other not reached symbols it can reach. Sort the non-reached non-terminals
 * by how many other not-reached symbols they reach, largest first. Print
 * the first not-reached non-terminal in this list. (if we are being verbose,
 * print all the non-reached non-terminals it reaches indented beneath it)
 * Now remove that non-terminal and all it reached from the unreached list
 * and move to the next one (but only print it if it is still in the unreached
 * list).
 *
 * Whew, this may be the most CPU ever devoted to a single error message!
 * 
 */
static
int     CompareSymLists(const void* A, const void* B)
    {
    SYMBOLS* a;
    SYMBOLS* b;

    a   = (SYMBOLS*)A;
    b   = (SYMBOLS*)B;
    return SymbolListCount(*b) - SymbolListCount(*a);
    }

void    CheckReachability(void)
    {
    TSymbol*    Symbol;
    int         iNonTerm, NNonTerms, NUnreached;
    SYMBOLS     Reached, Unreached;
    int         ErrorCount = 0;

    NNonTerms       = SymbolListCount(Globals.NonTerms);
    assert(NNonTerms > 0);
    Reached         = SymbolListCreate();
    Unreached       = SymbolListCreate();
    MarkReached(Reached, SymbolStart());
    

    /* make the complementary list: those not reached   */
    for(iNonTerm = 0; iNonTerm < NNonTerms; ++iNonTerm)
        {
        Symbol  = SymbolListGet(Globals.NonTerms, iNonTerm);
        if(!SymbolListContains(Reached, Symbol))
            SymbolListAdd(Unreached, Symbol);
        }

    /* if there were symbols not reached */
    NUnreached  = SymbolListCount(Unreached);
    if(NUnreached > 0)
        {
        SYMBOLS*   Sorted = calloc(NUnreached, sizeof(SYMBOLS));

        fprintf(stderr, "Out of %d non-terminals, %d are reachable, %d are unreachable:\n",
            SymbolListCountSig(Globals.NonTerms),
            SymbolListCountSig(Reached),
            SymbolListCountSig(Unreached)
        );

        /* build array of symbols each unreached symbol can reach */
        for(iNonTerm = 0; iNonTerm < NUnreached; ++iNonTerm)
            {
            SYMBOLS     Temp;
            TSymbol*    ThisUnreached = SymbolListGet(Unreached, iNonTerm);
            
            Sorted[iNonTerm]    = SymbolListCreate();
            MarkReached(Sorted[iNonTerm], ThisUnreached);
            /* retain only symbols on the unreached list */
            Temp    = SymbolListIntersect(Sorted[iNonTerm], Unreached);
            SymbolListDestroy(Sorted[iNonTerm]);
            Sorted[iNonTerm]    = Temp;
            }
        /* now sort the array by size */
        qsort(Sorted, NUnreached, sizeof(SYMBOLS), CompareSymLists);
        /* for each unreached symbol */
        for(iNonTerm=0; iNonTerm < NUnreached; ++iNonTerm)
            {
            Symbol  = SymbolListGet(Sorted[iNonTerm], 0);

            /* if we haven't already printed out this unreachable symbol */
            if(SymbolListContains(Unreached, Symbol))
                {
                int     iSymbol, NSymbols;

                /* print out unreachable symbol, with all the unreachables it
                 * reaches indented underneath it.
                 */
                NSymbols    = SymbolListCount(Sorted[iNonTerm]);
                for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
                    {
                    Symbol  = SymbolListGet(Sorted[iNonTerm], iSymbol);
                    fprintf(stderr, "%s'%.*s'\n", iSymbol ? "    " : "",
                            Symbol->Name.TextLen, Symbol->Name.Text);
                    /* remove printed symbol from further display */
                    SymbolListRemove(Unreached, Symbol);
                    }
                }
            SymbolListDestroy(Sorted[iNonTerm]);
            }
        free(Sorted);
        }

    SymbolListDestroy(Unreached);
    SymbolListDestroy(Reached);
    if(ErrorCount)
        Exit(-1, ERROR_UNREACHABLE_NONTERMINAL);
    }

static
int     Terminates(SYMBOLS TerminateList, SYMBOLS Visited, TSymbol* Symbol)
    {
    int     Result  = FALSE;

    if(SymbolIsTerminal(Symbol))        /* a terminal terminates, so there!             */
        Result  = TRUE;
    else if(SymbolIsNullable(Symbol))   /* deriving empty string counts as termination  */
        Result  = TRUE;
    else if(!SymbolIsTerminal(Symbol))
        {
        /* if it's a cycle */
        if(SymbolListContains(Visited, Symbol))
            Result  = FALSE;
        /* else, if already known to terminate */
        else if(SymbolListContains(TerminateList, Symbol))
            Result  = TRUE;
        /* else, have to check each rule, one by one */
        else
            {
            TRule**     Rover;
            TRule*      Rule;
    
            SymbolListAdd(Visited, Symbol);
            
            Rover   = Symbol->Rules;
            if(Rover)for(; *Rover; ++Rover)
                {
                int     Terminated, iItem, NItems;
                
                Rule        = *Rover;
                NItems      = SymbolListCount(Rule->Symbols);
                Terminated  = TRUE;
                for(iItem = 0; iItem < NItems; ++iItem)
                    {
                    TSymbol*    Item = SymbolListGet(Rule->Symbols, iItem);

                    if(!Terminates(TerminateList, Visited, Item))
                        {
                        Terminated  = FALSE;
                        break;
                        }
                    }
                if(Terminated)
                    {
                    Result  = TRUE;
                    break;
                    }
                }
            }
        }
    else
        assert(FALSE);

    return Result;
    }

/* CheckTermination() - verify that all nonterminals can terminate.
 *
 * Confirm that all nonterminals can produce either epsilon or a string
 * containing only terminals.
 *
 * Algorithm: mark nonterminals that are nullable or have a rule containing
 * only terminals or already marked nonterminals. Repeat until no more can
 * be marked. Any nonterminal not marked will not terminate.
 *
 * Unless verbosity was requested, we want to avoid reporting nontermination
 * caused by some other nonterminating symbol. Consider this grammar:
 *
 *    S : A ;
 *    A : A B ;
 *
 * A clearly does not terminate. The sole reason S does not terminate is
 * because A does not terminate. Hence, we would like to not (by default)
 * report S as a nonterminating symbol because that will distract attention
 * from the root cause.
 */

static
int     IsInCycle(SYMBOLS List, TSymbol* Target)
    {
    int     Result  = FALSE;    /* assume Symbol is not part of a cycle */
    RuleIt  Rhs;
    SYMBOLS Used;
    int     iUsed;

    Used    = SymbolListAdd(NULL, Target);
    for(iUsed = 0; iUsed < SymbolListCount(Used) && !Result; ++iUsed)
        for(Rhs = RuleItNew(SymbolListGet(Used, iUsed)); RuleIterate(&Rhs); )         /* iterate over RHS of next symbol */
            if(Rhs.ProdItem == Target)
                {
                Result  = TRUE;
                break;
                }
            else if(SymbolListContains(List, Rhs.ProdItem))
                Used    = SymbolListAddUnique(Used, Rhs.ProdItem);

    SymbolListDestroy(Used);

    return Result;
    }

int    CheckTermination(void)
    {
    int         NNonTerms;
    SYMBOLS     TerminateList       = NULL;
    SYMBOLS     NoTerminateList     = NULL;
    int         FoundMore;
    int         iLoop, MaxLoops;
    int         ErrorCount          = 0;
    SymIt       NonTerm, Bad;

    NNonTerms           = SymbolListCount(Globals.NonTerms);
    TerminateList       = SymbolListCreate();
    NoTerminateList     = SymbolListCreate();

    MaxLoops        = NNonTerms * NNonTerms;
    FoundMore       = TRUE;
    for(iLoop = 0; iLoop <= MaxLoops && FoundMore; ++iLoop)
        {
        NonTerm     = SymItNew(Globals.NonTerms);
        
        FoundMore   = FALSE;
        while(SymbolIterate(&NonTerm))
            {
            SYMBOLS     Visited;

            if(!SymbolListContains(TerminateList, NonTerm.Symbol))
                {
                assert(!SymbolIsTerminal(NonTerm.Symbol));
                Visited = SymbolListCreate();
                if(Terminates(TerminateList, Visited, NonTerm.Symbol))
                    {
                    TerminateList   = SymbolListAdd(TerminateList, NonTerm.Symbol);
                    FoundMore       = TRUE;
                    }
                SymbolListDestroy(Visited);
                }
            }
        }
    /* must have completed within MaxLoops or it's a bug */
    assert(FoundMore == FALSE);

    /* if not all symbols terminate */
    if(NNonTerms > SymbolListCount(TerminateList))
        {
fprintf(stderr, "Don't all terminate.\n");
        /* form list of symbols that don't terminate */
        NonTerm     = SymItNew(Globals.NonTerms);
        while(SymbolIterate(&NonTerm))
            {
            if(!SymbolListContains(TerminateList, NonTerm.Symbol))
                NoTerminateList    = SymbolListAdd(NoTerminateList, NonTerm.Symbol);
            }
    
        Bad     = SymItNew(NoTerminateList);
        /* now report on (possibly) redacted list */
        while(SymbolIterate(&Bad))
            {
    //        if(ShouldReportCycle(NonterminateList, Symbol))
    //        if(!SymbolListContains(TerminateList, Bad.Symbol))
            if(IsInCycle(NoTerminateList, Bad.Symbol))
                {
                ++ErrorCount;
                fprintf(stderr, "Non-terminal %s will not terminate.\n",
                        SymbolStr(Bad.Symbol));
                }
            }
        assert(ErrorCount > 0);
        }

    SymbolListDestroy(NoTerminateList);
    SymbolListDestroy(TerminateList);

    return ErrorCount;
    }

/* CheckOpsUsed() - warn if any operator/operands not actually used.
 *
 */
void    CheckOpsUsed(void)
    {
    int         NOperators, iOperator, iSymbol;
    SYMBOLS     NotUsed;
    TOperator*  Operator;
    TSymbol*    Symbol;

    NotUsed     = NULL;
    NOperators  = OperatorCount();

    for(iOperator = 0; iOperator < NOperators; ++iOperator)
        {
        Operator = OperatorGet(iOperator);

        for(iSymbol = 0; iSymbol < SymbolListCount(Operator->List); ++iSymbol)
            {
            Symbol  = SymbolListGet(Operator->List, iSymbol);
            if(Symbol && !Symbol->UsedInRule)
                {
                NotUsed = SymbolListAdd(NotUsed, Symbol);
                }
            }
        }
    if(NotUsed)
        {
        fprintf(stderr, "%d operators not used. ", SymbolListCount(NotUsed));
        fprintf(stderr, "Operator%s declared but not used:\n    ",
                (SymbolListCount(NotUsed) > 1) ? "s" : "");
        SymbolListDump(stderr,NotUsed, ", ");
        fprintf(stderr, "\n");
        SymbolListDestroy(NotUsed);
        }
    }

/* CheckFirstFirstClash() - find two rules with intersecting FIRST sets.
 *
 * This would be simple except we want to also detect FIRST/FIRST clashes
 * that would appear if we left-factored common prefixes.
 *
 * Consider this C99 fragment, where declaration_list is nullable:
 * compound_statement
 *	    : '{' '}'
 *	    | '{' statement_list '}'
 *	    | '{' declaration_list '}'
 *	    | '{' declaration_list statement_list '}'
 *	    ;
 * We do NOT want to complain that all the rules start with '{',
 * since that can be solved by left-factoring. However, because
 * declaration_list is nullable, the first and third rules contain
 * a FIRST/FIRST clash that would only appear AFTER left-factoring.
 */

/* ReportFirstFirstExample() - show why 'FirstClash' is in FIRST('Sym').
 *
 */
static
void    ReportFirstFirstExample(TSymbol* Sym, TSymbol* FirstClash)
    {
    static int  ForExample  = 0;
    int         iRule, NRules;
    TRule*      Rule;
    TSymbol*    FirstSym    = NULL;
    TSymbol*    Temp        = NULL;
    int         Intro;
    int         iProdItem, jProdItem, BestRule, MoreChoices;

    for(Intro=FALSE;;)
        {
        MoreChoices = FALSE;
        BestRule    = -1;
#if 0
        /* prefer simplest explanation: if there's a rule that starts with
         * the terminal 'FirstClash', then that will be easiest for the user
         * to understand.
         */
        for(iRule=0; iRule<Sym->NRules; ++iRule)
            {
            Rule        = Sym->Rules[iRule];
            FirstSym    = SymbolListGet(Rule->Symbols, 0);
            if(FirstSym == FirstClash)
                {
                if(!Intro)
                    {
                    fprintf(stdout, "%s:\n    %s", ForExample?"and":"For example", SymbolStr(Sym));
                    Intro   = ForExample  = TRUE;
                    }

                fprintf(stdout, " -> %s\n", SymbolStr(FirstClash));
                /* we explained it; we're done */
                return;
                }
            }
#endif
        /* we want to use the shortest example (nonterm closest to beginning of a rule) */
        for(iProdItem = 0; iProdItem >= 0; ++iProdItem)
            {
            /* look for symbol that is or can start with FirstClash */
            NRules  = RuleCount(Sym);
            for(iRule = 0; iRule < NRules; ++iRule)
                {
                int         PrefixNullable;

                Rule            = Sym->Rules[iRule];
                /* if rule too short, skip it */
                if(SymbolListCount(Rule->Symbols) <= iProdItem)
                    continue;
                PrefixNullable  = TRUE;
                for(jProdItem=0; jProdItem < iProdItem &&(Temp=SymbolListGet(Rule->Symbols, jProdItem)) != NULL && SymbolIsNullable(Temp); ++jProdItem)
                    if((Temp=SymbolListGet(Rule->Symbols, jProdItem)) != NULL && !SymbolIsNullable(Temp))
                        {
                        PrefixNullable  = FALSE;
                        break;
                        }
                if(!PrefixNullable)
                    continue;
                MoreChoices = TRUE;
                FirstSym    = SymbolListGet(Rule->Symbols, iProdItem);
                assert(FirstSym != NULL);
                /* if left-recursive rule, avoid infinite loop */
                if(iProdItem == 0 && SymbolIsEqual(FirstSym, Sym))
                    continue;
                if(SymbolIsEqual(FirstSym, FirstClash))  /* bingo: found (hopefully) shortest path to our terminal */
                    {
                    BestRule = iRule;
                    break;                  /* won't find anything better! */
                    }
                if(SymbolIsTerminal(FirstSym) == FALSE && SymbolListContains(FirstSym->First, FirstClash))
                    BestRule    = iRule;    /* but might find a better one */
                }
            if(BestRule != -1)
                {
                int     NullCount = 0;
                SYMBOLS Nullables = NULL;
                Rule            = Sym->Rules[BestRule];
                FirstSym        = SymbolListGet(Rule->Symbols, iProdItem);
                assert(FirstSym != NULL);
                if(!Intro)
                    {
                    fprintf(stdout, "%s:\n    %s ->", ForExample?"and":"For example", SymbolStr(Sym));
                    Intro   = ForExample  = TRUE;
                    }
                else
                    fprintf(stdout, "    %s ->", SymbolStr(Sym));
                for(jProdItem=0; jProdItem <= iProdItem; ++jProdItem)
                    {
                    Temp = SymbolListGet(Rule->Symbols, jProdItem);
                    if(Temp->Nullable && jProdItem < iProdItem)
                        Nullables   = SymbolListAdd(Nullables, Temp);
                    fprintf(stdout, " %s", SymbolStr(Temp));
                    }
                fprintf(stdout, "%s", jProdItem < (SymbolListCount(Rule->Symbols)-1)?" ...":"");
                NullCount   = SymbolListCount(Nullables);
                if(NullCount)
                    {
                    fprintf(stdout, "   (");
                    SymbolListDump(stdout, Nullables, ",and");
                    fprintf(stdout, " %s nullable)", (NullCount>1) ? "are all" : "is");
                    }
                fprintf(stdout, "\n");
                if(FirstSym == FirstClash)
                    return;
                Sym         = FirstSym;
                MoreChoices = FALSE;
                break;
                }
            }
        }
    }

/* ReportSkipIrrelevant() - report and skip irrelevant nonterminals.
 *
 * By "irrelevant", I mean that they are nullable and not the source
 * of the FIRST/FIRST clash.
 */
SYMBOLS  ReportSkipIrrelevant(SYMBOLS Irrelevant, TRule* Rule, TSymbol**Sym, int iProdItem, SYMBOLS Clash)
    {
    SYMBOLS MoreIntersect;

    MoreIntersect   = SymbolListIntersect((*Sym)->First, Clash);
    while(MoreIntersect == NULL)
        {
        assert(SymbolIsNullable(*Sym));  /* something's bad wrong if it's not nullable   */
        ++iProdItem;                    /* move to next RHS symbol                      */
        fprintf(stdout, "'%s' is nullable ", SymbolStr(*Sym));
        *Sym    = SymbolListGet(Rule->Symbols, iProdItem);
        assert(*Sym != NULL);
        MoreIntersect   = SymbolListIntersect((*Sym)->First, Clash);
        }
    SymbolListAddList(&Irrelevant, MoreIntersect);
    SymbolListDestroy(MoreIntersect);
    return Irrelevant;
    }

/* ReportFirstFirstClash() - turn rule conflict into intelligible message for user.
 */
static
void ReportFirstFirstClash(TSymbol* Symbol, TRule* RuleA, TRule* RuleB, int iProdItem, SYMBOLS Clash)
    {
    int         ClashCount  = SymbolListCount(Clash);
    TSymbol*    SymA        = SymbolListGet(RuleA->Symbols, iProdItem);
    TSymbol*    SymB        = SymbolListGet(RuleB->Symbols, iProdItem);
    TSymbol*    NonTerm     = NULL;
    TSymbol*    FirstClash  = SymbolListGet(Clash, 0);
    SYMBOLS     Irrelevant  = NULL;

    /* Show the two rules that conflict */
    fprintf(stdout, "Can't choose between two rules of '%s'\n", SymbolStr(Symbol));
    DumpRule(stdout, RuleA);
    DumpRule(stdout, RuleB);
    /* point out the common left prefix that is not a problem */
    if(iProdItem)
        {
        int iSym;
        
        fprintf(stdout, "Notice that after common left prefix of: ");
        for(iSym = 0; iSym < iProdItem; ++iSym)
            fprintf(stdout, " %s", SymbolStr(SymbolListGet(RuleA->Symbols, iSym)));
        fprintf(stdout, ",\n");
        }
    /* report&skip any nullable non-terminals that are irrelevant */
    Irrelevant  = ReportSkipIrrelevant(Irrelevant, RuleA, &SymA, iProdItem, Clash);
    Irrelevant  = ReportSkipIrrelevant(Irrelevant, RuleB, &SymB, iProdItem, Clash);
    if(Irrelevant)
        {
        fprintf(stdout, "\n");
        SymbolListDestroy(Irrelevant);
        }
    if(SymbolIsTerminal(SymA) == FALSE)
        NonTerm = SymA;
    else if(SymbolIsTerminal(SymB) == FALSE)
        NonTerm = SymB;
    else
        NonTerm = NULL;
    /* now detail how the non-terminal(s) produce a clashing symbol */
    if(SymbolIsEqual(SymA,SymB))
        {

        }
    else if(NonTerm)
        {
        if(SymbolIsTerminal(SymA) == FALSE && SymbolIsTerminal(SymB) == FALSE)
            fprintf(stdout, "Both '%s' and '%s' can start with ",
                SymbolStr(SymA), SymbolStr(SymB));
        else 
            fprintf(stdout, "'%s' can start with ", SymbolStr(NonTerm));
        if(ClashCount == 1)
            fprintf(stdout, "%s", SymbolStr(FirstClash));
        else if(ClashCount == 2)
            fprintf(stdout, "either %s or %s", SymbolStr(FirstClash), SymbolStr(SymbolListGet(Clash, 1)));
        else 
            {
            fprintf(stdout, "any of: ");
            SymbolListDump(stdout, Clash, ", ");
            }
        fprintf(stdout, ".  ");
        if(SymbolIsTerminal(SymA) == FALSE)
            ReportFirstFirstExample(SymA, FirstClash);
        if(SymbolIsTerminal(SymB) == FALSE)
            ReportFirstFirstExample(SymB, FirstClash);
        }

    fflush(stdout);
    exit(99);
    }

static
void    CheckEpsilonClash(TSymbol* NonTerm, TRule* Rule, TRule* Other, int PrefixLen)
    {
    int         NullableSuffix  = TRUE;
    int         iProdItem, NProdItems;
    TSymbol*    Symbol;

    for(iProdItem = PrefixLen; (Symbol=SymbolListGet(Rule->Symbols, iProdItem))!=NULL; ++iProdItem)
        if(!SymbolIsNullable(Symbol))
            {
            NullableSuffix  = FALSE;
            break;
            }
    if(NullableSuffix)
        {
        NProdItems  = SymbolListCount(Rule->Symbols);
        fprintf(stdout, "Conflicting rules in '%s'\n", SymbolStr(NonTerm));
        DumpRule(stdout, Other);
        DumpRule(stdout, Rule);
        if(PrefixLen >= 0)
            {
            fprintf(stdout, "After common prefix of: ");
            for(iProdItem=0; iProdItem < PrefixLen; ++iProdItem)
                fprintf(stdout, " %s", SymbolStr(SymbolListGet(Rule->Symbols, iProdItem)));
            fprintf(stdout, "\n");
            }
        fprintf(stdout, "this suffix is nullable: ");
        for(iProdItem=PrefixLen; iProdItem < NProdItems; ++iProdItem)
            fprintf(stdout, " %s", SymbolStr(Symbol=SymbolListGet(Rule->Symbols, iProdItem)));
        fprintf(stdout, "\n");
        if(PrefixLen == NProdItems - 1 && SymbolIsEqual(Symbol, NonTerm) && SymbolIsNullable(NonTerm))
            {
            fprintf(stdout, "Note: it appears that simply removing the shorter rule\n"
                    "would eliminate the ambiguity and be grammatically equivalent.\n"
                    );
            }
        exit(99);
        }
    }

/* CheckNullableRules() - see if two rules are both nullable.
 *
 * We already have a per-rule flag that tells us this, but
 * we want to make an effort to make the error messages more
 * intelligible.
 */
void    CheckNullableRules(TSymbol* NonTerm, TRule* RuleA, TRule* RuleB)
    {
    /* if they are both nullable (then we will be terminating) */
    if(RuleA->Nullable && RuleB->Nullable)
        {
        int     CountA, CountB;

        ErrorPrologue(ERROR_TWO_NULLABLE_RULES);
        CountA  = SymbolListCount(RuleA->Symbols);
        CountB  = SymbolListCount(RuleB->Symbols);
        if(CountA == 0 && CountB == 0)
            Error("'%s' contains two empty rules; can't choose between them.\n",
                    SymbolStr(NonTerm));
        else if(CountA == 0 || CountB == 0)
            {
            Error("'%s' contains an empty rule and a nullable rule; can't choose between them.\n",
                    SymbolStr(NonTerm));
            Error("The nullable rule is:\n    %s : ", SymbolStr(NonTerm));
            SymbolListDump(stderr, CountA?RuleA->Symbols:RuleB->Symbols, " ");
            Error("\n");
            }
        else
            Error("'%s' contains two nullable rules; can't choose between them.\n",
                    SymbolStr(NonTerm));
        if(CountA)
            DumpRule(stdout, RuleA);
        if(CountB)
            DumpRule(stdout, RuleB);
        ErrorEpilog(-1);
        }
    }

/* CheckFirstFirstClash() - look for rules we can't choose between.
 *
 * If a nonterminal has two rules with intersecting FIRST sets,
 * then we can't choose between them. This is complicated by
 * any later grammar transformation that could cause a FIRST/FIRST
 * clash to disappear. Obviously, left-factoring is one such
 * transformation, since it's whole purpose is to remove a
 * FIRST/FIRST clash. Left recursion removal is another case:
 *
 *     lines
 *         :
 *         | lines line
 *         ;
 *
 * Here, because 'lines' is nullable, then it can both start with
 * and be followed by a 'line'. But that problem will go away when
 * the grammar is transformed to remove the left recursion.
 */
void    CheckFirstFirstClash(void)
    {
    int         iRule, jRule, NRules, iProdItem, MinCount, IsRecursiveA, IsRecursiveB;
    TRule*      RuleA;
    TRule*      RuleB;
    TSymbol*    SymA;
    TSymbol*    SymB;
    SymIt       NonTerm = SymItNew(Globals.NonTerms);

    Dump("CheckFirstFirstClash()\n");

    /* for each nonterminal */
    while(SymbolIterate(&NonTerm))
        {
        if(NonTerm.Symbol->OperatorTrigger)
            continue;
        /* for each rule of this nonterminal */
        NRules  = RuleCount(NonTerm.Symbol);
        for(iRule=0; iRule < NRules-1; ++iRule)
            {
            RuleA       = NonTerm.Symbol->Rules[iRule];
            IsRecursiveA    = (SymbolListGet(RuleA->Symbols, 0) == NonTerm.Symbol);
            /* compare rule to all others that follow */
            for(jRule=iRule+1; jRule < NRules; ++jRule)
                {
                RuleB   = NonTerm.Symbol->Rules[jRule];
                CheckNullableRules(NonTerm.Symbol, RuleA, RuleB);
                IsRecursiveB    = (SymbolListGet(RuleB->Symbols, 0) == NonTerm.Symbol);
                /* compare left recursive rules only to other left recursive rules */
                if(IsRecursiveA != IsRecursiveB)
                    continue;
                /* RewriteGrammar() will handle common left prefixes later */
                if(CommonLeft(NonTerm.Symbol, RuleA->Symbols, RuleB->Symbols))
                    continue;
                MinCount    = SymbolListCount(RuleA->Symbols);
                if(MinCount > SymbolListCount(RuleB->Symbols))
                    MinCount    = SymbolListCount(RuleB->Symbols);
                for(iProdItem=0; iProdItem < MinCount; ++iProdItem)
                    {
                    SYMBOLS     Clash;
                    SYMBOLS     FirstA=NULL, FirstB=NULL;
                    
                    /* don't compare first symbol of left-recursive rules */
                    if(IsRecursiveA && iProdItem == 0)
                        continue;
                    SymA    = SymbolListGet(RuleA->Symbols, iProdItem);
                    SymB    = SymbolListGet(RuleB->Symbols, iProdItem);
                    if(SymA == SymB)
                        continue;   /* skip over common left prefix */
                    /* form FIRST() sets for these rule suffixes */
                    FirstA  = RuleFirst(NonTerm.Symbol, RuleA, iProdItem);
                    FirstB  = RuleFirst(NonTerm.Symbol, RuleB, iProdItem);
                    Clash   = SymbolListIntersect(FirstA, FirstB);
                    SymbolListDestroy(FirstA);
                    SymbolListDestroy(FirstB);
                    if(Clash)
                        {
                        ReportFirstFirstClash(NonTerm.Symbol, RuleA, RuleB, iProdItem, Clash);
//                        SymbolListDestroy(Clash);
                        }
                    break;
                    }
                if(SymbolListCount(RuleA->Symbols) > MinCount)
                    CheckEpsilonClash(NonTerm.Symbol, RuleA, RuleB, iProdItem);
                else if(SymbolListCount(RuleB->Symbols) > MinCount)
                    CheckEpsilonClash(NonTerm.Symbol, RuleB, RuleA, iProdItem);
                }
            }
        }
    Dump("CheckFirstFirstClash() done\n");
    }

/* WhyFollow() - explain why terminal Term is in FOLLOW(NonTerm)
 *
 * For Term to be in FOLLOW(NonTerm), there must be some rule
 * of a nonterminal X where NonTerm appears in the rhs of X and:
 *     1) is followed by a string 'alpha', where FIRST(alpha) contains Term
 * or
 *     2) alpha is nullable (or nonexistent) and FOLLOW(X) contains Term
 *
 * We first locate a rhs occurrence of NonTerm that meets these criteria.
 * If FIRST(alpha) contains Term, then we are done. Otherwise, we recurse
 * to explain why FOLLOW(X) contains Term. As we unwind the recursion, we
 * can print out a derivation (the derived string is stored in Derived)
 * that explains in some detail why exactly Term is in FOLLOW(NonTerm).
 */
static
int    WhyFollow(TSymbol* Target, TSymbol* Term, SYMBOLS Derived, TSymbol* SPtr)
    {
    int         iProdItem, jProdItem, kProdItem, NProdItems, DLR;
    TRule*      Rule;
    TRule**     Rover;
    SymIt       NonTerm = SymItNew(Globals.NonTerms);

    DumpVerbose("WhyFollow('%s', %s)\n", SymbolStr(Target), SymbolStr(Term));
    /* for every nonterminal */
    while(SymbolIterate(&NonTerm))
        {
        if(NonTerm.Symbol->OperatorTrigger) /* but skip LR(0) rules */
            continue;
        /* for every rule of this nonterminal */
        Rover = NonTerm.Symbol->Rules;
        if(Rover) for(; *Rover; ++Rover)
            {
            DLR         = FALSE;    /* assume rule is not direct left recursive */
            Rule        = *Rover;
            /* for each rhs symbol of this rule */
            NProdItems  = SymbolListCount(Rule->Symbols);
            for(iProdItem=0; iProdItem < NProdItems; ++iProdItem)
                {
                TSymbol*    Symbol  = SymbolListGet(Rule->Symbols, iProdItem);
                TSymbol*    Adjacent;
                SYMBOLS     AlphaFirst;

                /* direct left recursion symbol is not what we want... */
                if(iProdItem == 0 && Symbol == NonTerm.Symbol)
                    {
                    DLR     = TRUE;
//printf("DLR=TRUE for rule %d\n", iRule);
//                    continue;
                    }

                if(Symbol != Target)
                    continue;
                /* At last, we found the target nonterminal in the rhs of a rule.
                 * So set Adjacent to symbol that follows our target non-terminal.
                 * (Still works fine even if no other symbols to right of this one.)
                 */
                /* skip any action items */
                for(kProdItem=iProdItem+1; (Adjacent=SymbolListGet(Rule->Symbols, kProdItem)) != NULL; ++kProdItem)
                    if(!SymbolIsAction(Adjacent))
                        break;
                    else
                        {
                        printf("at pos %d, %s is action!\n", kProdItem, SymbolStr(Adjacent));
                        }
                Adjacent    = SymbolListGet(Rule->Symbols, kProdItem);
                AlphaFirst  = RuleFirst(NonTerm.Symbol, Rule, kProdItem);
#if 1
printf("Found symbol at pos %d in a rule for %s -> ", iProdItem, SymbolStr(NonTerm.Symbol));
SymbolListDump(stdout, Rule->Symbols, " ");
printf("\nAlphaFirst(%d)=", kProdItem);
SymbolListDump(stdout, AlphaFirst, " ");
printf("\nFOLLOW(%s)=", SymbolStr(NonTerm.Symbol));
SymbolListDump(stdout, NonTerm.Symbol->Follow, " ");
printf("\n");
#endif
                /* if this rule could explain why Term is in FOLLOW(Target) */
                if( SymbolListContains(AlphaFirst, Term)
                ||  ( RuleNullable(Rule, kProdItem)
                  &&  SymbolListContains(NonTerm.Symbol->Follow, Term)
                    )
                  )
                    {
printf("\n%d Found rule to explain it (k=%d):  %s ", SymbolListContains(AlphaFirst, Term), kProdItem, SymbolStr(NonTerm.Symbol));
DumpRule(stdout, Rule);
                    /* NonTerm -> ... Target alpha
                     * if Term is not in FIRST(alpha), then must explain
                     * why it is in FOLLOW(NonTerm) by recursing
                     */
                    if(!SymbolListContains(AlphaFirst, Term))
                        {
                        jProdItem = WhyFollow(NonTerm.Symbol, Term, Derived, SPtr);
                        /* here is where we are unwinding after recursing */
                        Error("%s -> ", SymbolStr(NonTerm.Symbol));
                        SymbolListDump(stderr, Rule->Symbols, "{ ");
                        if(kProdItem < NProdItems)
                            {
                            Error(" (where ");
                            while((Symbol=SymbolListGet(Rule->Symbols, kProdItem)) != NULL)
                                Error("%s ", SymbolStr(Symbol));
                            Error("is nullable)");
                            }
                        Error("\n");
                        SymbolListReplace(Derived, jProdItem, Rule->Symbols);
                        Error("    [ ");
                        SymbolListDump(stderr, Derived, "{ ");
                        Error(" ]\n");
                        return iProdItem + jProdItem;
                        }
                    /* NonTerm -> ... Target Adjacent ...
                     * At this point, Adjacent is either Term or else
                     * FIRST(Adjacent) contains Term.
                     */
                    else if(Adjacent && Adjacent != Term)
                        {
                        assert(SymbolListContains(Adjacent->First, Term));
                        Error(", where '%s' can start with a '%s':\n", SymbolStr(Adjacent), SymbolStr(Term));
                        }
                    else
                        Error(":\n");   /* finish off "Consider this derivation" */
                    /* here is where the topmost derivation is emitted*/
                    Error("%s -> ", SymbolStr(NonTerm.Symbol));
                    SymbolListDump(stderr, Rule->Symbols, "{ ");
                    Error("\n");
                    SymbolListCopy(Derived, Rule->Symbols);
                    Error("    [ ");
                    SymbolListDump(stderr, Rule->Symbols, "{ ");
                    Error(" ]\n");
                    if(Symbol == NULL)
                        {
                        Error("%s -> ", SymbolStr(NonTerm.Symbol));
                        SymbolListDump(stderr, Rule->Symbols, "{ ");
                        Error("\n");
                        SymbolListReplace(Derived, 0, Rule->Symbols);
                        Error("    [ ");
                        SymbolListDump(stderr, Derived, "{ ");
                        Error(" ]\n");
                        }
                    return iProdItem;
                    }
                if(AlphaFirst)
                    SymbolListDestroy(AlphaFirst);
                }
            }
        }
    fflush(stdout);
    fflush(stderr);
    assert(FALSE);  /* should not reach here */
    return FALSE;
    }

/* CheckSuffix() - try to distinguish suffixes of a common left prefix.
 *
 * We found two rules with a common left prefix. To make sure we will
 * later be able to factor that common prefix out (and end up with an
 * LL(1) grammar), we need to know that the suffixes can be distinguished
 * from each other.
 */

static
int    SuffixFirst(SYMBOLS* First, SYMBOLS List, int Pos)
    {
    TSymbol*    Symbol;
    int         Nullable = TRUE;

    while((Symbol=SymbolListGet(List, Pos)) != NULL)
        {
        *First = SymbolListAddFirst(*First, Symbol);
        if(Symbol->Nullable)
            ++Pos;
        else
            {
            Nullable    = FALSE;
            break;
            }
        }
    return Nullable;
    }
static
void CheckSuffix(TSymbol* NonTerm, SYMBOLS AList, int iA, SYMBOLS BList, int iB)
    {
    int     ANullable, BNullable;
    SYMBOLS FirstA = NULL;
    SYMBOLS FirstB = NULL;
    SYMBOLS Clash  = NULL;

    ANullable  = SuffixFirst(&FirstA, AList, iA);
    BNullable  = SuffixFirst(&FirstB, BList, iB);

    Clash   = SymbolListIntersect(FirstA, FirstB);
    assert(SymbolListCount(Clash) == 0);
    
    if(ANullable && BNullable)
        {
        SYMBOLS  Temp;

        ErrorPrologue(ERROR_SUFFIXES_NULLABLE);
        Error("Can't choose between two rules:\n    %s : ", SymbolStr(NonTerm));
        SymbolListDump(stderr, AList, "{ ");
        Error("\n    %s : ", SymbolStr(NonTerm));
        SymbolListDump(stderr, BList, "{ ");
        Error("\nAfter the common left prefix of:\n    ");
        Temp    = SymbolListTruncate(SymbolListCopy(NULL, AList), iA);
        SymbolListDump(stderr, Temp, "{ ");
        Error("\nboth suffixes are nullable.\n");
        ErrorEpilog(-1);
        }
    assert(!(ANullable && BNullable));
    }            


/* CommonLeft() - check two rules for common left prefixes.
 *
 * Two errors are checked for:
 *     A) two rules that are identical
 *     B) a common left prefix that contains embedded actions
 *
 * If no errors were encountered, the length of the common prefix
 * (if any) of the two rules is returned.
 */
int    CommonLeft(TSymbol* NonTerm, SYMBOLS AList, SYMBOLS BList)
    {
    int         iA, nA, iB, nB;
    TSymbol*    A;
    TSymbol*    B;
    SYMBOLS     Common = NULL;
    int         MatchCount;
    int         ActionCount, FoundActions, LastSymbolMatched;


    DumpVerbose(".   CommonLeft('%s') comparing rules:\n.     -> ", SymbolStr(NonTerm));
    SymbolListDump(stdout, AList, " ");
    DumpVerbose("\n.     -> ");
    SymbolListDump(stdout, BList, " ");
    DumpVerbose("\n");

    nA          = SymbolListCount(AList);
    nB          = SymbolListCount(BList);
//    assert(nA > 0 && nB > 0);

    ActionCount         = 0;
    FoundActions        = FALSE;
    LastSymbolMatched   = FALSE;
    A   = B     = NULL;
    for(iA=iB=0; iA < nA || iB < nB; ++iA,++iB)
        {
        /* advance to next "real" symbol in AList (if any) */
        for(A = NULL; iA < nA; ++iA)
            {
            A   = SymbolListGet(AList, iA);
            if(SymbolIsAction(A))
                {
                A   = NULL;
                ++ActionCount;
                }
            else
                break;
            }
        /* advance to next "real" symbol in BList (if any) */
        for(B = NULL; iB < nB; ++iB)
            {
            B   = SymbolListGet(BList, iB);
            if(SymbolIsAction(B))
                {
                B   = NULL;
                ++ActionCount;
                }
            else
                break;
            }
        /* if there was another symbol in both productions */
        if(A != NULL || B != NULL)
            {
            /* If both productions share another prefix symbol */
            if(A == B)
                {
                LastSymbolMatched   = TRUE;
                if(ActionCount)
                    FoundActions    = TRUE;
                Common  = SymbolListAdd(Common, A);
                continue;
                }
            else
                {
                LastSymbolMatched   = FALSE;
                break;
                }
            }
        /* else, we must have exhausted both lists */
        assert(iA >= nA && iB >= nB);
        }
    MatchCount  = SymbolListCount(Common);

    if(LastSymbolMatched == TRUE)
        {
        ErrorPrologue(ERROR_RULES_ARE_IDENTICAL);
        Error("Nonterminal '%s' has two or more rules with identical symbols:\n", SymbolStr(NonTerm));
        SymbolListDump(stderr, Common, " ");
        Error("\n");
        ErrorEpilog(-1);
        }
    /* */
    else if(MatchCount > 0)
        {
        Dump("    # of common left symbols=%d: ", SymbolListCount(Common));
        SymbolListDump(stdout, Common, " ");
        printf("\n");
        if(FoundActions)
            {
            ErrorPrologue(ERROR_COMMON_PREFIX_CONTAINS_ACTION);
            Error("Nonterminal '%s': %s\n",
                    SymbolStr(NonTerm),
                    "two rules share a common prefix containing embedded actions\n");
            Error("  -> ");
            SymbolListDump(stderr, AList, " ");
            Error("\n");
            Error("  -> ");
            SymbolListDump(stderr, BList, " ");
            Error("\n");
            Exit(-1, ERROR_COMMON_PREFIX_CONTAINS_ACTION);
            }
        CheckSuffix(NonTerm, AList, iA, BList, iB);
        }
    if(Common)
        SymbolListDestroy(Common);
//fprintf(stderr, "    LastSymbolMatched=%d, MatchCount=%d\n", LastSymbolMatched, MatchCount);

    return MatchCount;
    }

/* CheckFirstFollowClash() - give reasonable message when FIRST(N) intersects FOLLOW(N)
 *
 * Suppose N is a nullable nonterminal whose FIRST set and FOLLOW set
 * both contain one or more of the same terminals (I'll use 'x' in this
 * example). Then the grammar is not LL(1), since when N is on top of
 * the stack and the next input terminal is 'x', we can't decide whether
 * to let N eat this 'x' or choose its nullable alternative so that
 * whatever comes after the N can eat the 'x' (which we know is possible,
 * else 'x' would not be in FOLLOW(N)).
 *
 * However, it is often quite tedious for the user to figure out why
 * 'x' is in FOLLOW(N), so this function takes pains to explain why.
 *
 * Basically, if 'x' is in FOLLOW(N), then we must be able to find
 * some rule like this:
 *
 * M  : ... N alpha
 *
 * where either FIRST(alpha) contains 'x', or alpha is nullable
 * and FOLLOW(M) contains 'x'. If FIRST(alpha) contains 'x', then
 * we report which symbol in alpha caused that to be true. Otherwise,
 * we recurse to indicate why FOLLOW(M) contains 'x'.
 * 
 */
void    CheckFirstFollowClash(void)
    {
    int         iProdItem, NProdItems;
    TRule*      Rule;
    TRule**     Rover;
    TSymbol*    X;
    TSymbol*    Y;
    SymIt       NonTerm = SymItNew(Globals.NonTerms);

    Dump("CheckFirstFollowClash()\n");
    /* for every nonterminal */
    while(SymbolIterate(&NonTerm))
        {
        /* Well, not "every" nonterminal */
        if(SymbolIsAction(NonTerm.Symbol))
            continue;
        /* for each rule of this non-terminal */
        Rover   = NonTerm.Symbol->Rules;
        if(Rover) for(; *Rover; ++Rover)
            {
            /* for each production item of this rule */
            Rule        = *Rover;
            NProdItems  = SymbolListCount(Rule->Symbols);
            for(iProdItem=0; iProdItem < NProdItems; ++iProdItem)
                {
                SYMBOLS     Clash, SuffixFirst;

                X       = SymbolListGet(Rule->Symbols, iProdItem);
                if(!X->Nullable || !X->FirstFollowClash)
                    continue;
                /* ignore first symbol in simple left recursive rule ???*/
                if(iProdItem == 0 && X == NonTerm.Symbol)
                    continue;
                Clash   = SymbolListIntersect(X->First, X->Follow);
                if(Clash)
                    {
                    TSymbol*    Clash1 = SymbolListGet(Clash, 0);
                    TSymbol*    First  = NULL;
                    
                    ErrorPrologue(ERROR_A_NULLABLE_B_CLASH);
                    Error("Can't decide whether '%s' should consume a '%s' or nothing\n"
                          "(it's nullable), "
                          "since it can also be followed by a '%s'.\nConsider this derivation",
                          SymbolStr(X), SymbolStr(Clash1), SymbolStr(Clash1));
                    ReportFirstFirstExample(X, Clash1);
//Error("WhyFollow(%s, %s)!!!!!!\n", SymbolStr(X), SymbolStr(SymbolListGet(Clash, 0)));
                    WhyFollow(X, Clash1, SymbolListCreate(), First);
                    SymbolListDestroy(Clash);
                    if(First)
                        {
                        ReportFirstFirstExample(First, Clash1);
                        }
                    ErrorEpilog(0);
                    }
                else
                    continue;
                Y   = SymbolListGet(Rule->Symbols, iProdItem+1);

                SuffixFirst = RuleFirst(NonTerm.Symbol, Rule, iProdItem+1);
                Clash   = SymbolListIntersect(X->First, SuffixFirst);
                SymbolListDestroy(SuffixFirst);

                if(Clash)
                    {
                    ErrorPrologue(ERROR_A_NULLABLE_B_CLASH);
                    Error("Clash on %s %s in: %s -> ", SymbolStr(X), SymbolStr(Y), SymbolStr(NonTerm.Symbol));
                    SymbolListDump(stderr, Rule->Symbols, " ");
                    Error("\n'%s' is nullable, but both '%s' and '%s' can start with: ",
                            SymbolStr(X), SymbolStr(X), SymbolStr(Y));
                    SymbolListDump(stderr, Clash, " ");
                    Error("\n");
                    ErrorEpilog(-1);
                    }
                }
            }
        }
    Dump("CheckFirstFollowClash() returns\n");
    }

/* CheckLeftRecursion() - identify/report instances of left recursion.
 *
 * The primary motivation for this step is to give a better error
 * message than what would emerge when we try to construct the LL(1)
 * parsing table.
 */
typedef struct  TState
    {
    int         iRule;
    int         iRhs;
    TSymbol*    Suspect;
    TRule*      Rule;
    }           TState;

static
int     CheckLeftPopStack(TState *State, int StackTop, TState* Stack)
    {
//printf("pop '%.*s'\n", State->Suspect->Name.TextLen, State->Suspect->Name.Text);
    if(--StackTop >= 0)
        {
        TSymbol*    Suspect = State->Suspect;

        *State  = Stack[StackTop];
        if(Suspect->Nullable)
            ++State->iRhs;
        else
            {
            ++State->iRule;
            State->iRhs     = -1;
            }
        }

    return StackTop;
    }

static
void    ReportLeftRecursion(TState* Stack, int StackTop)
    {
    int i;
    
    fprintf(stderr, "Left recursion (x* indicates x is nullable):\n");
    for(i = 0; i < StackTop; ++i)
        {
        int     iProdItem;
        TRule*  Rule    = Stack[i].Rule;
        
        fprintf(stderr, "    %.*s: ", Stack[i].Suspect->Name.TextLen, Stack[i].Suspect->Name.Text);
        for(iProdItem = 0; iProdItem < SymbolListCount(Rule->Symbols); ++iProdItem)
            {
            TSymbol*    Symbol  = SymbolListGet(Rule->Symbols, iProdItem);
            fprintf(stderr, "%.*s", Symbol->Name.TextLen, Symbol->Name.Text);
            if(Symbol->Nullable)
                fprintf(stderr, "* ");
            else
                fprintf(stderr, " ");
            }
        fprintf(stderr, "\n");
        }
    }

static
int     CheckLeft(TSymbol* NonTerm, TState* Stack, SYMBOLS Tried)
    {
    TState  State       = {0};
    int     ErrorCount  = 0;
    int     StackTop    = 0;

    /* State is logically Stack[StackTop] */
    State.iRule     = -1;
    State.Suspect   = NonTerm;
    while(StackTop >= 0)
        {
        if(StackTop < 0)    /* if no more symbols on stack      */
            return ErrorCount;
        /* if starting new non-terminal         */
        else if(State.iRule < 0)
            {
            /* see if new entry proves left-recursion */
            if(StackTop > 0 && State.Suspect == NonTerm)
                {
                ++ErrorCount;
                ReportLeftRecursion(Stack, StackTop);
                StackTop  = CheckLeftPopStack(&State, StackTop, Stack);
                /*??? then what ???*/
                }
            /* else if we have already gone down this path before */
            else if(SymbolListContains(Tried, State.Suspect) || State.Suspect->OperatorTrigger)
                StackTop  = CheckLeftPopStack(&State, StackTop, Stack);
            /* else, get ready to walk through rules in this suspect    */
            else
                {
                SymbolListAdd(Tried, State.Suspect);
                State.iRule = 0;
                State.iRhs  = -1;
                }
            }
        else if(State.iRule >= RuleCount(State.Suspect))
            StackTop  = CheckLeftPopStack(&State, StackTop, Stack);
        /* if starting a new rule */
        else if(State.iRhs == -1)
            {
            /* if no more rules in this non-terminal */
            if(State.iRule >= RuleCount(State.Suspect))
                StackTop  = CheckLeftPopStack(&State, StackTop, Stack);
            else
                {
                State.Rule  = State.Suspect->Rules[State.iRule];
                State.iRhs  = 0;
                }
            }
        /* if no more symbols in this RHS */
        else if(State.iRhs >= SymbolListCount(State.Rule->Symbols))
            {
            State.iRhs  = -1;
            ++State.iRule;
            }
        /* else, we are examining a RHS symbol in a rule from the current non-terminal */
        else
            {
            TSymbol*    Symbol = SymbolListGet(State.Rule->Symbols, State.iRhs);

            if(SymbolGetBit(Symbol, SYM_TERMINAL))
                {
                State.iRhs  = -1;
                ++State.iRule;
                }
            /* else, get ready to push new symbol on stack */
            else
                {
//printf("push '%.*s'\n", Symbol->Name.TextLen, Symbol->Name.Text);
                Stack[StackTop++]   = State;
                State.Suspect       = Symbol;
                State.iRule         = -1;
                }
            }
        }

    return ErrorCount;
    }

static
void    ReportLeftRecursionClash(TSymbol* Lhs, TRule* Rule, SYMBOLS Clashes)
    {
    fprintf(stdout, "%s can both start with and be followed by: ", SymbolStr(Lhs));
    SymbolListDump(stdout, Clashes, ", ");
    fprintf(stdout, "\n");
    fprintf(stdout, "which is not allowed for this left-recursive rule:\n%s -> ", SymbolStr(Lhs));
    SymbolListDump(stdout, Rule->Symbols, " ");
    fprintf(stdout, "\n");
    exit(999);
    }


/* SimpleLeftRecursion() - return true if it's left recursion we handle.
 *
 * We handle "immediate self recursion", of the form:
 *
 *    A -> A <stuff>
 *
 * so we don't want to warn about it. However, note that <stuff> must
 * not be empty or nullable -- that case will already have been detected
 * by CheckCircularity() before we are called.
 * 
 * Note the impending transformation to:
 * 
 *     A -> <stuff> `A
 *    `A -> <epsilon>
 *        | <stuff> `A
 *
 * Also, FIRST(<stuff>) must not intersect FOLLOW(A). We will exert
 * effort to produce an intelligent error message for such cases.
 */
static
int     SimpleLeftRecursion(TSymbol* Lhs)
    {
    int         Result;
    TRule**     Rover;

    Result      = FALSE;    /* assume it's not simple left recursion */

    /* for each production of this non-terminal */
    Rover   = Lhs->Rules;
    if(Rover) for(; *Rover; ++Rover)
        {
        int     NSymbols, iSymbol;
        TRule*  Rule    = *Rover;

        assert(Rule != NULL);

        NSymbols    = SymbolListCount(Rule->Symbols);
        for(iSymbol=0; iSymbol < NSymbols; ++iSymbol)
            {
            TSymbol*    Rhs = SymbolListGet(Rule->Symbols, iSymbol);

            assert(Rhs != NULL);
            if(SymbolIsAction(Rhs))
                continue;
            if(Rhs == Lhs)  /* if first "real" symbol same as left-hand side */
                {
                SYMBOLS     Clashes;
                TSymbol*    Symbol;

                Symbol      = SymbolListGet(Rule->Symbols, 1);
                Clashes     = SymbolListIntersect(Symbol->First, Lhs->Follow);
                if(SymbolListCount(Clashes))
                    ReportLeftRecursionClash(Lhs, Rule, Clashes);
                SymbolListDestroy(Clashes);
                }
            }
        }
    return Result;
    }

void    CheckLeftRecursion(void)
    {
    int         ErrorCount;
    int         iNonTerm, NNonTerms;
    TState*     Stack;

    if(Globals.Dump)
        printf("CheckLeftRecursion!\n");

    NNonTerms   = SymbolListCount(Globals.NonTerms);
    Stack       = (TState*)malloc(sizeof(TState)*(NNonTerms+1));
    assert(Stack != NULL);

    ErrorCount  = 0;
    /* Check each non-terminal for left-recursion */
    for(iNonTerm = 0; iNonTerm < NNonTerms; ++iNonTerm)
        {
        TSymbol*    NonTerm;

        NonTerm     = SymbolListGet(Globals.NonTerms, iNonTerm);
        if(!NonTerm->LeftRecursive)
            {
            SYMBOLS Tried = SymbolListCreate();

            ErrorCount += CheckLeft(NonTerm, Stack, Tried);

            SymbolListDestroy(Tried);
            }
        }

    if(ErrorCount)
        ErrorExit(ERROR_LEFT_RECURSION, "%d instance%s of left recursion.",
              ErrorCount, ErrorCount > 1 ? "s" : "");
    free(Stack);
    }

